#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int ElemType;
typedef struct {
    ElemType *elem;
    int TableLen;
}SSTable;
//初始化顺序表
void ST_Init(SSTable &ST,int len)
{
    ST.TableLen=len;
    ST.elem=(ElemType*)malloc(sizeof(ElemType) * ST.TableLen);
    srand(time(NULL));  //随机生成数
    for (int j = 0; j < ST.TableLen; j++)
    {
        ST.elem[j]=rand() % 100; //为了随机生成的书都在0-99之间
    }
}
void ST_Print(SSTable ST)
{
    for (int i = 0; i < ST.TableLen; ++i) {
        printf("%3d",ST.elem[i]);
    }
    printf("\n");
}
void swap(int &a,int &b)
{
    int temp;
    temp=a;
    a=b;
    b=temp;
}
void SelectSort(ElemType *A,int len)
{
    int min,i,j;
    for(i=0;i<len-1;i++)
    {
        min=i;
        for(j=i+1;j<len;j++)
        {
            if(A[j]<A[min])
                min=j;
        }
        if(i!=min)
            swap(A[i],A[min]);
    }
}
void AdjustDown(ElemType *A,int k,int len)
{
    int dad=k;
    int son=2*dad+1;
    while (son<len)
    {
        if(son+1<len&&A[son]<A[son+1])
        {
            son++;
        }
        if(A[son]>A[dad])
        {
            swap(A[son],A[dad]);
            dad=son;
            son=2*dad+1;
        } else
            break;
    }
}
void HeapSort(ElemType *A,int len)
{
    int i,j;
    for(i=len/2-1;i>=0;i--)
    {
        AdjustDown(A,i,len);
    }
    swap(A[0],A[len-1]);
    for(j=len-1;j>1;j--)
    {
        AdjustDown(A,0,j);
        swap(A[0],A[j-1]);
    }
}
void Merge(ElemType *A,int low,int mid,int high)
{
    static ElemType B[10];
    int i,j,k;
    for(i=0;i<=high;i++)
    {
        B[i]=A[i];
    }
    for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++)
    {
        if(B[i]<B[j])
            A[k]=B[i++];
        else
            A[k]=B[j++];
    }
    while (i<=mid)
        A[k++]=B[i++];
    while (j<=high)
        A[k++]=B[j++];
}
void MergeSort(ElemType *A,int low,int high)
{
    if(low<high)
    {
        int mid=(low+high)/2;
        MergeSort(A,low,mid);
        MergeSort(A,mid+1,high);
        Merge(A,low,mid,high);
    }
}
int main() {
    SSTable ST;
    ST_Init(ST,10);
    ElemType A[10];
    for (int i = 0; i < ST.TableLen; ++i) {
        scanf("%d",&A[i]);
    }
    //内存copy接口，当你copy整型数组，或者浮点型时，使用memcpy，不能用strcpy，初试考memcpy概率很低
    memcpy(ST.elem,A,sizeof(A)); //这是为了降低调试难度，每次数组数据固定而设计
    ST_Print(ST);
    SelectSort(ST.elem,10);
    ST_Print(ST);
    // 12 63 58 95 41 35 65  0 38 44
    memcpy(ST.elem,A,sizeof(A)); //这是为了降低调试难度，每次数组数据固定而设计
    HeapSort(ST.elem,10);
    ST_Print(ST);

    memcpy(ST.elem,A,sizeof(A)); //这是为了降低调试难度，每次数组数据固定而设计
    MergeSort(ST.elem,0,9);
    ST_Print(ST);
    return 0;
}
